package com.zxy.leetcode._00000_00099._00020_00029;

/**
 * https://leetcode-cn.com/problems/divide-two-integers/
 *
 * 两数相除
 * 给定两个整数，被除数 dividend 和除数 divisor。
 * 将两数相除，要求不使用乘法、除法和 mod 运算符。
 * 返回被除数 dividend 除以除数 divisor 得到的商。
 * 整数除法的结果应当截去（truncate）其小数部分，
 * 例如：truncate(8.345) = 8 以及 truncate(-2.7335) = -2
 *
 * 思路：二分查找
 * https://leetcode-cn.com/problems/divide-two-integers/solution/po-su-de-xiang-fa-mei-you-wei-yun-suan-mei-you-yi-/
 *
 * 举个例子：11 除以 3 。
 * 首先11比3大，结果至少是1， 然后我让3翻倍，就是6，发现11比3翻倍后还要大，
 * 那么结果就至少是2了，那我让这个6再翻倍，得12，11不比12大，吓死我了，
 * 差点让就让刚才的最小解2也翻倍得到4了。但是我知道最终结果肯定在2和4之间。
 * 也就是说2再加上某个数，这个数是多少呢？我让11减去刚才最后一次的结果6，剩下5，
 * 我们计算5是3的几倍，也就是除法，看，递归出现了。
 */
public class Test00029 {

    public static void main(String[] args) {
        Test00029 test = new Test00029();
        System.out.println(test.divide(10, 3));
        System.out.println(test.divide(7, -3));
        System.out.println(test.divide(Integer.MIN_VALUE, -1));
    }

    public int divide(int dividend, int divisor) {
        if (dividend == 0) {
            return 0;
        }
        if (divisor == 1) {
            return dividend;
        }
        if (divisor == -1) {
            if (dividend == Integer.MIN_VALUE) {
                return Integer.MAX_VALUE;
            }
            return 0 - dividend;
        }

        long a = dividend;
        long b = divisor;
        boolean sign = a>0&&b>0 || a<0&&b<0;
        a = a > 0 ? a : -a;
        b = b > 0 ? b : -b;

        return sign ? divide(a, b) : -divide(a, b);
    }

    // 非递归求解
    public int divide(long a, long b) {
        if (a < b) {
            return 0;
        }

        long tmpB = b;
        int count = 1;
        int sum = 0;
        while (a >= b) {
            b <<= 1;
            if (a > b) {
                count <<= 1;
            }else {
                sum += count;
                // 数据还原
                b >>= 1;
                a -= b;
                b = tmpB;
                count = 1;
            }
        }

        return sum;
    }

    // 递归求解
    public int divide2(long a, long b) {
        if (a < b) {
            return 0;
        }

        long tmp = b;
        int count = 1;
        b <<= 1;
        while (a >= b) {
            count <<= 1;
            b <<= 1;
        }
        b >>= 1;
        return count + divide2(a - b, tmp);
    }

}
